# coding=utf-8
r"""
Words of all kinds

AUTHORS:
    -- Arnaud Bergeron
    -- Amy Glen
    -- Sébastien Labbé
    -- Franco Saliola
    
EXAMPLES:
We define the set of words over 'a' and 'b'.
    sage: W = Words('ab'); W
    Words over ['a', 'b']
    
Then we can build some words in the set:
    sage: W('abba')
    word: abba
    
If you try to use symbols that are not the alphabet of the set you get an error:
    sage: W([1, 2])
    Traceback (most recent call last):
    ...
    IndexError: symbol not in alphabet: 1
    
You can also build infinite words backed by a function or an iterator!
    sage: def f(n):
    ...     if n % 2 == 1:
    ...         return 'a'
    ...     else:
    ...         return 'b'
    ...
    sage: W(f)
    Infinite word over ['a', 'b']
"""
#*****************************************************************************
#       Copyright (C) 2008 Arnaud bergeron <abergeron@gmail.com>,
#                          Amy Glen <amy.glen@gmail.com>,       
#                          Sébastien Labbé <slabqc@gmail.com>,
#                          Franco Saliola <saliola@gmail.com>,
#
#  Distributed under the terms of the GNU General Public License version 2 (GPLv2)
#
#  The full text of the GPLv2 is available at:
#
#                  http://www.gnu.org/licenses/
#*****************************************************************************
from array import array
from itertools import tee, islice, ifilter, ifilterfalse, imap, izip, \
                      starmap, count, repeat, dropwhile, chain, cycle
from weakref import WeakValueDictionary
from sage.structure.sage_object import SageObject
from sage.sets.set import Set
from sage.rings.infinity import infinity
from sage.misc.latex import latex
from sage.words.alpha import Alphabet
from sage.words.word_content import MakeContent, is_Content
from sage.words.disjoint_set import DisjointSet
from sage.words.utils import *

def Word(data=None, alphabet=None):
    r"""
    Returns a word over the given alphabet. 

    INPUT:
        data -- An iterable (list, string, iterator) or a function defined
            on nonnegative integers that yields the symbols of the word.
        alphabet -- An iterable yielding symbols in their comparative
            order. If alphabet is None and data is a string or list, then
            the symbols appearing in data, ordered by Python's builtin
            sorted function, is used as alphabet.

    OUTPUT:
        A FiniteWord or InfiniteWord object. 

    NOTE:
        Essentially, this function just returns Words(alphabet)(data).

    EXAMPLES:
    0. The empty word.        
        sage: Word()
        word:

    1. Finite words from strings.
        sage: Word("abbabaab")
        word: abbabaab

        sage: Word("abbabaab", alphabet="abc")
        word: abbabaab

    2. Finite words from lists.
        sage: Word(["a", "b", "b", "a", "b", "a", "a", "b"])
        word: abbabaab

        sage: Word([0,1,1,0,1,0])
        word: 011010

    3. Finite words from functions.
        sage: f = lambda n : n % 2
        sage: Word(f, [0, 1])[:17]
        word: 01010101010101010

    4. Finite words from iterators.
        sage: def tmword():
        ...    thuemorse = WordMorphism('a->ab,b->ba')
        ...    w = thuemorse('a')[:]
        ...    i = 0
        ...    while w:
        ...        for x in thuemorse(w[i]):
        ...            yield x
        ...        else:
        ...            w *= thuemorse(w[i+1])
        ...            i += 1
        sage: Word(tmword(), alphabet="ab")[:32]
        word: abbabaabbaababbabaababbaabbabaab

    5. Infinite words from functions.
        sage: f = lambda n : n % 2
        sage: Word(f, alphabet=[0, 1])
        Infinite word over [0, 1]

    6. Infinite words from iterators.
        sage: def tmword():
        ...    thuemorse = WordMorphism('a->ab,b->ba')
        ...    w = thuemorse('a')[:]
        ...    i = 0
        ...    while w:
        ...        for x in thuemorse(w[i]):
        ...            yield x
        ...        else:
        ...            w *= thuemorse(w[i+1])
        ...            i += 1
        sage: Word(tmword(), alphabet="ab")
        Infinite word over ['a', 'b']

    TESTS:
        sage: f = lambda n : n % 2
        sage: Word(f)
        Traceback (most recent call last):
          ...
        TypeError: alphabet is required for words not defined by lists or strings
        sage: Word(f, alphabet=[1])
        Infinite word over [1]
    """
    # If the alphabet is not specified, then try to build one from data.
    if alphabet is None:
        if data is None:
            alphabet = []
        elif isinstance(data, (str,list)):
            alphabet = sorted(set(data))
        else:
            raise TypeError, "alphabet is required for words not defined by lists or strings"
    # Return the word object
    return Words(alphabet)(data)

class Words(SageObject):
    r"""
    Defines the set of words over an alphabet.
    
    INPUT:
        alpha -- either an instance of Alphabet or an argument suitable to build one.
    
    OUTPUT:
        words -- the set object

    EXAMPLES:
    You build a set like this:
        sage: W = Words('ab'); W
        Words over ['a', 'b']
        
    We can now ask our set what is its alphabet,
        sage: W().alphabet()
        Alphabet: ['a', 'b']
        
    and build words from the set by calling the set with appropriate arguments
        sage: W('abba')
        word: abba
    
    If we try using unknown symbols, the word will be rejected
        sage: W('abc')
        Traceback (most recent call last):
          ...
        IndexError: symbol not in alphabet: 'c'
    """
    def __new__(cls, alpha):
        r"""
        TESTS:
            sage: wab = Words('ab')
            sage: wab == loads(dumps(wab))
            True
            sage: wab is Words('ab')
            True
        """
        if not isinstance(alpha, Alphabet):
            try:
                alpha = Alphabet(alpha)
            except (TypeError, ValueError):
                raise TypeError, "alpha is not an alphabet and cannot be used to build one"
        if alpha not in cls._words_cache:
            res = super(Words, cls).__new__(cls)
            res._alpha = alpha
            cls._words_cache[alpha] = res
        return cls._words_cache[alpha]
    
    _words_cache = WeakValueDictionary()
    
    def __getnewargs__(self):
        r"""
        Support for pickle
        
        TESTS:
            sage: Words('abc').__getnewargs__()
            (Alphabet: ['a', 'b', 'c'],)
        """
        return (self._alpha,)
    
    def __getstate__(self):
        r"""
        Support for pickle
        
        TESTS:
            sage: Words('abc').__getstate__()
        """
        pass
        
    def __setstate__(self):
        r"""
        Support for pickle
        
        TESTS:
            sage: Words('abc').__setstate__()
        """
        pass
    
    def alphabet(self):
        r"""
        This function returns the alphabet over which the set is defined.
        
        EXAMPLES:
            sage: Words('abc').alphabet()
            Alphabet: ['a', 'b', 'c']
        """
        return self._alpha
        
    def dimension(self):
        r"""
        Return the size of the alphabet.
        
        EXAMPLES:
            sage: Words('abcdef').dimension()
            6
            sage: Words('').dimension()
            0
        """
        return len(self.alphabet())
    
    def __call__(self, obj=None, part=slice(None), format=None):
        r"""
        TESTS:
            sage: from itertools import repeat, count, imap
            sage: W = Words('ab')
            sage: W(format='empty')
            word: 
            sage: W(['a', 'b'], format='empty')
            Traceback (most recent call last):
              ...
            TypeError: trying to build an empty word with something other than None
            sage: W(['a', 'b', 'b'])
            word: abb
            sage: W(['a', 'b', 'b'], format='list')
            word: abb
            sage: W(10, format='list')
            Traceback (most recent call last):
              ...
            TypeError: trying to build a word backed by a list with a sequence not providing the required operations
            sage: Words([0, 1])(lambda x: x%2)
            Infinite word over [0, 1]
            sage: W = Words([0, 1, 2])
            sage: W(lambda x: x%3, slice(0,10))
            word: 0120120120
            sage: W(repeat(1))
            Infinite word over [0, 1, 2]
            sage: Words(xrange(10))(count(), slice(10))
            word: 0123456789
            sage: Words(xrange(10))(count(), slice(10, 0, -2))
            word: 97531
            sage: W(1)
            word: 1
            sage: W('a', format='symbol')
            Traceback (most recent call last):
            ...
            ValueError: symbol ('a') not in alphabet
            sage: W([0, 1])
            word: 01
        """
        
        if format is None:
            if is_Content(obj):
                format = 'content'
            elif obj in self.alphabet():
                format = 'symbol'
        
        if format == 'symbol':
            if obj not in self.alphabet():
                raise ValueError, "symbol (%r) not in alphabet" % obj
            obj = (obj,)
            format = 'list'
        
        if not slice_ok(part):
            raise TypeError, "part is not a slice or has wrong types for elements"
        if format == 'content':
            if not is_Content(obj):
                raise TypeError, "trying to build a word based on raw content with a non-content"
            content = obj
        elif is_Word(obj) and obj.parent() is self:
            return obj[part]
        else:
            content = MakeContent(obj, self.alphabet().to_int, format=format, part=part)
        if haslen(content):
            return FiniteWord(content, self)
        else:
            return InfiniteWord(content, self)
        
    def __contains__(self, w):
        r"""
        Returns whether w is included in this set or not.
        
        INPUT:
            w -- a word
            
        OUTPUT:
            boolean -- is w in the set
            
        EXAMPLES:
            sage: Wab = Words('ab')
            sage: Wabc = Words('abc')
            sage: abba = Wab('abba')
            sage: abc = Wabc('abc')
            sage: abba in Wab
            True
            sage: abba in Wabc
            True
            sage: abc in Wabc
            True
            sage: abc in Wab
            False
            sage: Wabc('baab') in Wab # todo: not implemented
            True
        """
        if not is_Word(w):
            return False
        if w._parent == self:
            return True
        else:
            return self >= w._parent
    
    def __le__(self, other):
        r"""
        Returns whether other is a superset of this word set or not.
        
        The ordering of the symbols is ignored for this.
        
        EXAMPLES:
            sage: Words('abc') <= Words('daefbgc')
            True
            sage: Words('abc') <= Words('abc')
            True
            sage: Words('abc') <= Words('ac')
            False
            sage: Words('abc') <= Words([1, 2, 3])
            False
        """
        if not isinstance(other, Words):
            return NotImplemented
        return self.alphabet() <= other.alphabet()
    
    def __ge__(self, other):
        r"""
        Returns whether other is a subset of this word set or not.
        
        The ordering of the symbols is ignored for this.
        
        EXAMPLES:
            sage: Words('abc') >= Words('daefbgc')
            False
            sage: Words('abc') >= Words('abc')
            True
            sage: Words('abc') >= Words('ac')
            True
            sage: Words('abc') >= Words([1, 2, 3])
            False
        """
        if not isinstance(other, Words):
            return NotImplemented
        return self.alphabet() >= other.alphabet()
        
    def _repr_(self):
        r"""
        Returns a string representation of the object
        
        TESTS:
            sage: Words('ab')._repr_()
            "Words over ['a', 'b']"
        """
        return "Words over %s" % self._alpha.string_rep()
    
    def _latex_(self):
        r"""
        Returns a latex representation of the object
        
        TESTS:
            sage: Words('ab')._latex_()
            '[\\text{a}, \\text{b}]^*'
        """
        return latex(self._alpha) + "^*"

def is_Word(obj):
    r"""
    Returns true if obj is a word.
    
    EXAMPLES:
        sage: is_Word(33)
        False
        sage: is_Word(Word('abba'))
        True
    """
    return isinstance(obj, GenericWord)

def is_FiniteWord(obj):
    r"""
    Returns true if obj is a finite word.
    
    EXAMPLES:
        sage: is_FiniteWord(33)
        False
        sage: is_FiniteWord(Word('baab'))
        True
    """
    return isinstance(obj, FiniteWord)

class GenericWord(SageObject):
    def __init__(self, content, parent):
        r"""
        Initialize the GenericWord object with the parent relationship.
        
        TESTS:
            sage: g = sage.words.word.GenericWord(sage.words.word_content.MakeContent(''), Words('abc'))
            sage: g = sage.words.word.GenericWord(33, Words('abc'))
            Traceback (most recent call last):
            ...
            TypeError: bogus content
            sage: g = sage.words.word.GenericWord(sage.words.word_content.MakeContent(''), 33)
            Traceback (most recent call last):
            ...
            TypeError: the parent must be an instance of Words
            sage: loads(dumps(g))
            Word
        """
        if not isinstance(parent, Words):
            raise TypeError, "the parent must be an instance of Words"
        self._parent = parent
        if not is_Content(content):
            raise TypeError, "bogus content"
        self._content = content
    
    def __iter__(self):
        r"""
        Returns an iterator over the symbols of the word
        
        EXAMPLES:
            sage: W = Words('ab')
            sage: w = W('abba')
            sage: list(w)           # indirect test
            ['a', 'b', 'b', 'a']
        """
        return imap(self.alphabet().to_sym, self._content)
    
    def __getitem__(self, key):
        r"""
        TESTS:
            sage: w = Words('012345')('012345')
            sage: w[:]
            word: 012345
            sage: w[3]
            '3'
        """
        res = self._content[key]
        if is_Content(res):
            return self.parent()(res, format='content')
        else:
            return self.parent().alphabet().to_sym(res)
    
    def _repr_(self):
        r"""
        Returns a string representation of the object
        
        TESTS:
            sage: sage.words.word.GenericWord(sage.words.word_content.MakeContent(''), Words('ab'))._repr_()
            'Word'
        """
        return "Word"
        
    def parent(self):
        r""" 
        Returns the parent object from which the word was created.
        
        EXAMPLES:
            sage: W = Words('ab')
            sage: w = W('abba')
            sage: w.parent()
            Words over ['a', 'b']
            sage: w.parent() is W
            True
        """
        return self._parent
    
    def alphabet(self):
        r"""
        Returns the alphabet of the parent.
        
        EXAMPLES:
            sage: Words('abc')('abbabaab').alphabet()
            Alphabet: ['a', 'b', 'c']
        """
        return self._parent.alphabet()
    
    def coerce(self, other):
        r"""
        Returns a pair of words in a common set or raises an exception
        
        This function begins by checking if both words have the same parent.
        If this is the case, then no work is done and both words are returned
        as-is.
        
        Otherwise it will attempt to convert other to the domain of self.
        If that fails, it will attempt to convert self to the domain of 
        other.  If both attempts fail, it raises a TypeError to signal 
        failure.
        
        EXAMPLES:
            sage: W1 = Words('abc'); W2 = Words('ab')
            sage: w1 = W1('abc'); w2 = W2('abba'); w3 = W1('baab')
            sage: w1.parent() is w2.parent()
            False
            sage: a, b = w1.coerce(w2)
            sage: a.parent() is b.parent()
            True
        """
        if self._parent != other._parent:
            try:
                other = self.parent()(other)
            except:
                try:
                    self = other.parent()(self)
                except:
                    raise TypeError, "no coercion rule between %r and %r" % (self.alphabet(), other.alphabet())
        return self, other

#######################################################################
#                                                                     #
#                           Finite words                              #
#                                                                     #
#######################################################################

class FiniteWord(GenericWord):
    def __init__(self, content, parent):
        r"""
        TESTS:
            sage: sage.words.word.FiniteWord(sage.words.word_content.MakeContent('0123', int), Words('abcd'))
            word: abcd
        """
        super(FiniteWord, self).__init__(content, parent)
    
    def __len__(self):
        r"""
        Return the length of the word.
        
        TESTS:
            sage: len(Words('ab')('abba'))
            4
        """
        return len(self._content)
    
    def _repr_(self):
        r"""
        Returns a string representation of the object
        
        TESTS:
            sage: Word('abc')._repr_()
            'word: abc'
            sage: Word([0, 1, 0, 1, 1] * 10)._repr_()
            'Finite word of length 50 over [0, 1]'
        """
        if len(self) < 40:
            return str(self)
        else:
            return "Finite word of length %s over %s" % (len(self), self.alphabet().string_rep())

    def __mul__(self, other):
        r"""
        Concatenates two words.
        
        EXAMPLES:
            sage: W = Words([0, 1])
            sage: W() * W(lambda x:x%2, slice(3))
            word: 010
            sage: Words([0, 1, 2])(lambda x:x%3, slice(3)) * Words('01234')('01234')
            Traceback (most recent call last):
            ...
            TypeError: no coercion rule between Alphabet: [0, 1, 2] and Alphabet: ['0', '1', '2', '3', '4']
        """
        self, other = self.coerce(other)
        c = self._content.concatenate(other._content)
        return self.parent()(c, format='content')
        
    def __pow__(self, exp):
        r"""
        Return the $exp$-th power of self.

        If $exp$ is $\infty$, returns the infinite periodic word of base self.
        Otherwise, $|w|\cdot exp$ must be an non negative integer.

        INPUT:
            exp  -- an integer, a rational, a float number or plus infinity.

        OUTPUT:
            word -- the $exp$-th power of self. 
                
        EXAMPLES:

        You can take non negative integer powers :
            sage: w = Word(range(6)); w
            word: 012345
            sage: w^2
            word: 012345012345
            sage: w^1
            word: 012345
            sage: w^0
            word: 
            sage: w^(-1)
            Traceback (most recent call last):
            ...
            ValueError: The exponent must be non negative.

        You can take non negative rational powers :
            sage: w = Word(range(6)); w
            word: 012345
            sage: w^(.5)
            word: 012
            sage: w^(1/3)
            word: 01
            sage: (w*w)^(1/2) == w
            True
            sage: w^(5/2)
            word: 012345012345012
            
        ...but the length of the word times the exponent must be an integer :
            sage: w = Word(range(6))
            sage: w^(1/4)
            Traceback (most recent call last):
            ...
            ValueError: Power of the word is not defined on the exponent 1/4: the length of the word (6) times the exponent (1/4) must be a positive integer
            
        You can take infinite power :
            sage: w = Word(range(6)); w
            word: 012345
            sage: w^oo
            Infinite word over [0, 1, 2, 3, 4, 5]
            sage: (w^oo)[10000000:20000000]                         
            Finite word of length 10000000 over [0, 1, 2, 3, 4, 5]
            sage: (w^oo)[10000000:10000020]
            word: 45012345012345012345
            sage: Word()^oo
            word: 
        """
        if exp is infinity:
            if self.is_empty():
                return self
            else:
                return self.parent()(lambda n: self[n % len(self)])
        
        nbCaracteres = len(self)*exp
        
        #If exp*|self| is not an integer
        if int(nbCaracteres) != nbCaracteres :
            raise ValueError, "Power of the word is not defined on the \
exponent %s: the length of the word (%s) times the exponent \
(%s) must be a positive integer"  % (exp, len(self), exp)

        #If exp is negative
        elif exp < 0 :
            raise ValueError, "The exponent must be non negative."
        
        return self.parent()(lambda n: self[n % len(self)], part=slice(int(nbCaracteres)) )
        
    
    def __str__(self):
        r"""
        Returns the full string representation of the word.
        
        TESTS:
            sage: Word('abc').__str__()
            'word: abc'
            sage: Words([0, 1])([0, 1, 0, 0, 1] * 10).__str__()
            'word: 01001010010100101001010010100101001010010100101001'
        """
        return 'word: ' + self.string_rep()
    
    def string_rep(self):
        r"""
        Returns the raw sequence of symbols as a string.
        
        EXAMPLES:
            sage: Words('ab')('abbabaab').string_rep()
            'abbabaab'
            sage: Words(range(2))([0, 1, 0, 0, 1]).string_rep()
            '01001'
        """
        return ''.join(map(str, self))
    
    def __cmp__(self, other):
        """
        Compares two words with lexicographically according to the order
        defined in the common alphabet.  Provides for all normal 
        comparison operators.
        
        EXAMPLES:
            sage: W1 = Words('12'); W2 = Words('123')
            sage: W2('123').__cmp__(W1('1211')) > 0
            True
            sage: W1('2111').__cmp__(W2('12')) > 0
            True
            sage: W2('123').__cmp__(W2('123')) == 0
            True
            sage: W1('121').__cmp__(W2('121')) == 0
            True
            sage: W2('123').__cmp__(W1('22')) < 0
            True
            sage: W1('122').__cmp__(W2('32')) < 0
            True
            sage: W1('122').__cmp__(Words('ab')('abba'))  # todo: not implemented
            Traceback (most recent call last):
            ...
            TypeError: no coercion rule between Alphabet: ['1', '2'] and Alphabet: ['a', 'b']
        """
        if not is_Word(other):
            return NotImplemented
        try:
            self, other = self.coerce(other)
        except TypeError:
            return NotImplemented
        for (c1, c2) in izip(self._content, other._content):
            r = c1 - c2
            if r != 0: return r
        return len(self) - len(other)
    
    def __hash__(self):
        r"""
        Returns the hash for this word.
        
        TESTS:
             sage: h = hash(Word('abc'))    # indirect test
             sage: Word('abc').__hash__() == Word('abc').__hash__()
             True
        """
        res = 5381
        for s in self._content:
            res = ((res << 5) + res) + s
        return res
        
    def is_empty(self):
        """
        Return True if the length of the receiver is zero and False otherwise.
        
        EXAMPLES:
            sage: W=Words('ab')
            sage: W().is_empty()
            True
            sage: W('a').is_empty()
            False
        """
        return len(self)==0
    
    def is_prefix_of(self, other):
        """
        w.is_prefix_of(other) -> True or False
        
        Return True if w is prefix of other.
        
        EXAMPLES:
            sage: V = Words('0123456789')
            sage: w = V('0123456789')
            sage: y = V('012345')
            sage: y.is_prefix_of(w)
            True
            sage: w.is_prefix_of(y) 
            False
            sage: W = Words('ab')
            sage: w.is_prefix_of(W())
            False
            sage: W().is_prefix_of(w)
            True
            sage: W().is_prefix_of(W())
            True
        """
        return self == other[:len(self)]
    
    def is_proper_prefix_of(self, other):
        """
        Returns true if the reciever is a proper prefix of other.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W('12').is_proper_prefix_of(W('123'))
            True
            sage: W('12').is_proper_prefix_of(W('12'))
            False
            sage: W().is_proper_prefix_of(W('123'))
            True
            sage: W('123').is_proper_prefix_of(W('12'))
            False
            sage: W().is_proper_prefix_of(W())
            False
        """
        return self.is_prefix_of(other) and len(self) < len(other)
    
    def is_suffix_of(self, other):
        """
        w.is_suffix_of(other) -> True or False
        
        Return True if w is suffix of other.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: w = W('0123456789')
            sage: y = W('56789')
            sage: y.is_suffix_of(w)
            True
            sage: w.is_suffix_of(y)
            False
            sage: W('579').is_suffix_of(w)
            False
            sage: W().is_suffix_of(y)
            True
            sage: w.is_suffix_of(W())    
            False
            sage: W().is_suffix_of(W())
            True
        """
        return self.is_empty() or self == other[-len(self):]
    
    def is_proper_suffix_of(self, other):
        """
        Returns true of the reciever is a proper suffix of other.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('23').is_proper_suffix_of(W('123'))
            True
            sage: W('12').is_proper_suffix_of(W('12'))
            False
            sage: W().is_proper_suffix_of(W('123'))
            True
            sage: W('123').is_proper_suffix_of(W('12'))
            False
        """
        return self.is_suffix_of(other) and len(self) < len(other)
    
    def reversal(self):
        """
        w.reversal() -> FiniteWord
        
        return the reversal of the receiver
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('124563').reversal()
            word: 365421
        """
        return self[::-1]
    
    def is_palindrome(self, f=None):
        r"""
        Return True if self is a palindrome (or a $f$-palindrome).
        
        INPUT:
            f -- involution (default: None) on the alphabet of self. It must 
                 be something that WordMorphism's contructor understand 
                 (dict, str, ...).
            
        OUTPUT:
            boolean -- if f is None, whether self is a palindrome.
                       otherwise, whether self is a $f$-palindrome.
        
        DEFINITION :
            - In French
            "Soit $f : \Sigma \rightarrow \Sigma$ une involution qui s'étend 
            évidemment à un morphisme sur $\Sigma^*$. On dit que $w\in\Sigma^*$ 
            est un \emph{$f$-pseudo-palindrome} [1], ou plus 
            simplement un \emph{$f$-palindrome}, si $w=f(\til{w})$."
            (extrait de [2])
                        
            - In English
            Let $f : \Sigma \rightarrow \Sigma$ be an involution that extend 
            to a morphism on $\Sigma^*$. We say that $w\in\Sigma^*$ is a
            \emph{$f$-palindrome} if $w=f(\til{w})$ [2]. 
            
            Also called \emph{$f$-pseudo-palindrome} [1].
            
        REFERENCES :
            [1] Anne, V., L. Q. Zamboni et I. Zorca, Palindromes and Pseudo-Palindromes
            in Episturmian and Pseudo-Palindromic Infinite Words, in : S. Brlek, 
            C. Reutenauer (Eds.), Words 2005, Publications du LaCIM, Vol. 36 (2005) 91--100.
            [2] Labbé, Sébastien. Propriétés combinatoires des $f$-palindromes,  
            Mémoire de maîtrise en Mathématiques, Montréal, UQAM, 2008, 109 pages.

        EXAMPLES :
        Some palindromes...
            sage: W=Words('abcdefghijklmnopqrstuvwxyz I')
            sage: W('esope reste ici et se repose').is_palindrome()
            False
            sage: W('esoperesteicietserepose').is_palindrome()
            True
            sage: W('I saw I was I').is_palindrome()
            True
            sage: Word('abbcbba').is_palindrome()
            True
            sage: Word('abcbdba').is_palindrome()
            False

        Some $f$-palindromes...
        You can use a str :
            sage: Word('aababb').is_palindrome('a->b,b->a')
            True
            sage: Word('abacbacbab').is_palindrome('a->b,b->a,c->c')
            True
            
        You can use WordMorphism :
            sage: f = WordMorphism('a->b,b->a')
            sage: Word('aababb').is_palindrome(f)
            True
        
        You can use a dictionary :
            sage: f = {'a':'b','b':'a'}
            sage: Word('aababb').is_palindrome(f) #todo : not implemented
            True
            
        self must be in the domain of the involution :
            sage: f = WordMorphism('a->a')
            sage: Word('aababb').is_palindrome(f)
            Traceback (most recent call last):
            ...
            ValueError: self must be in the domain of the given involution
            
        The given involution must be an involution :
            sage: f = WordMorphism('a->b,b->b')
            sage: Word('abab').is_palindrome(f)
            Traceback (most recent call last):
            ...
            ValueError: f must be an involution
            
        TESTS:
            sage: Y = Words('ab')
            sage: Y().is_palindrome()
            True
            sage: Y('a').is_palindrome()
            True
            sage: Y('ab').is_palindrome()
            False
            sage: Y('aba').is_palindrome()
            True
            sage: Y('aa').is_palindrome() 
            True
            sage: E = 'a->b,b->a'
            sage: Y().is_palindrome(E)
            True
            sage: Y('a').is_palindrome(E)
            False
            sage: Y('ab').is_palindrome(E)
            True
            sage: Y('aa').is_palindrome(E)
            False
            sage: Y('aba').is_palindrome(E)
            False
            sage: Y('abab').is_palindrome(E)
            True
        """
        if f is None:
            l = len(self)
            return self[:l/2] == self[l/2 + l%2:].reversal()
            
        from sage.words.morphism import WordMorphism
        f = WordMorphism(f)
        
        if self not in f.domain():
            raise ValueError, "self must be in the domain of "\
                                 +"the given involution"
        
        if not f.is_involution():
            raise ValueError, "f must be an involution"
            
        l = len(self)
        return self[:l/2 + l%2] == f(self[l/2:].reversal()) 
            
    def lps(self, f=None):
        r"""
        Return the longest palindrome (or $f$-palindrome) suffix of self.
        
        INPUT:
            f -- involution (default: None) on the alphabet of self. It must 
                 be something that WordMorphism's contructor understand 
                 (dict, str, ...).
            
        OUTPUT:
            word -- If f is None, the longest palindrome suffix of self;
                    otherwise, the longest $f$-palindrome suffix of self.

        EXAMPLES:
            sage: Word('0111').lps()
            word: 111
            sage: Word('011101').lps()
            word: 101
            sage: Word('6667').lps()
            word: 7
            sage: Word('abbabaab').lps()
            word: baab
            sage: Word().lps()
            word: 
            sage: Word('abbabaab').lps('a->b,b->a')
            word: abbabaab
        """
        for i in range(len(self)+1):
            fact = self[i:]
            if fact.is_palindrome(f=f):
                return fact
        
    def _lps(self, l=None, f=None):
        r"""
        Return the longest palindrome (or $f$-palindrome) suffix of self.
                
        INPUT:
            f -- involution (default: None) on the alphabet of self. It must 
                 be something that WordMorphism's contructor understand 
                 (dict, str, ...).
            l -- integer (default: None) the length of the longest palindrome 
                 suffix of self[:-1]
            
        OUTPUT:
            word -- If f is None, the longest palindrome suffix of self;
                    otherwise, the longest $f$-palindrome suffix of self.
                
        EXAMPLES :
            sage: W = Words('1234')
            sage: w = W('33412321')
            sage: w._lps(3)
            word: 12321
            sage: Y = Words('01')
            sage: w = Y('01101001')
            sage: w._lps(l=2)
            word: 1001
            sage: w._lps()          
            word: 1001
            sage: w._lps(None)
            word: 1001
            sage: w._lps(4) #No verification of the given length of the precedent lps
            word: 101001
            sage: Y()._lps(2)
            Traceback (most recent call last):
            ...
            IndexError: word index out of range
            sage: v=Words('ab')('abbabaab')
            sage: pal=v[:0] 
            sage: for i in range(1,len(v)+1): 
            ...     pal=v[:i]._lps(len(pal))
            ...     print pal
            ...   
            word: a
            word: b
            word: bb
            word: abba
            word: bab
            word: aba
            word: aa
            word: baab
            sage: v=Words('ab')('abbabaab')
            sage: pal=v[:0] 
            sage: for i in range(1,len(v)+1): 
            ...     pal=v[:i]._lps(len(pal),'a->b,b->a')
            ...     print pal
            ...   
            word: 
            word: ab
            word: 
            word: ba
            word: ab
            word: baba
            word: bbabaa
            word: abbabaab
        """
        if l == None:
            return self.lps(f=f)
                    
        #If l == len(w[:-1]), there is no shortcut
        if len(self) == l + 1:
            return self.lps(f=f)
        
        #Obtain the letter to the left (g) and to the right (d) of the 
        #precedent lps of self
        g = self[-l-2]
        d = self[-1]
        
        #If the word g*d is a $f$-palindrome, the result follows
        if self.parent()([g, d]).is_palindrome(f=f):
            return self[-l-2:]
        
        #Otherwise, the length of the lps of self is smallest than l+2
        else:
            return self[-l-1:].lps(f=f)
                
    def palindromic_lacunas_study(self, f=None):
        r"""
        Returns interesting statistics about longest ($f$-)palindromic suffixes
        and lacunas of self (see [1] and [2]).
                    
        Note that a word $w$ has at most $|w| + 1$ different palindromic factors (see [4]).

        INPUT:
            f -- involution (default: None) on the alphabet of self. It must 
                 be something that WordMorphism's contructor understand 
                 (dict, str, ...).
                             
        OUTPUT:
            list -- list of the length of the longest palindromic
                    suffix (lps) for each non empty prefix of self;
            list -- list of all the lacunas, i.e. positions where there is no
                    unioccurent lps ;
            set -- set of palindromic factors of self.
                   
        REFERENCES:
            [1] Blondin Mass\'e, A., S. Brlek et S. Labb\'e, 
            Palindromic lacunas of the Thue-Morse word, Proc. GASCOM 2008 
            (June 16-20 2008, Bibbiena, Arezzo-Italia), 53--67.
            [2] Blondin Mass\'e, A., S. Brlek, A. Frosini, S. Labb\'e et S. Rinaldi,
            Reconstructing words from a fixed palindromic length sequence, 
            Proc. TCS 2008, 5th IFIP International Conference on Theoretical 
            Computer Science (September 8-10 2008, Milano, Italia), accepted.
            [3] Labbé, Sébastien. Propriétés combinatoires des $f$-palindromes,  
            Mémoire de maîtrise en Mathématiques, Montréal, UQAM, 2008, 109 pages.
            [4] Droubay, X., J. Justin et G. Pirillo, Episturmian words and 
            some constructions of de Luca and Rauzy, {\em Theoret. Comput. Sci.} 
            {\bf 255} (2001) 539--553.

        EXAMPLES:
            sage: W=Words('ab')
            sage: a,b,c = W('abbabaabbaab').palindromic_lacunas_study()                                         
            sage: a
            [1, 1, 2, 4, 3, 3, 2, 4, 2, 4, 6, 8]
            sage: b
            [8, 9]
            sage: c          # random order
            set([word: , word: b, word: bab, word: abba, word: bb, word: aa, word: baabbaab, word: baab, word: aba, word: aabbaa, word: a])
            sage: a,b,c = W('abbabaab').palindromic_lacunas_study(f='a->b,b->a')                                         
            sage: a
            [0, 2, 0, 2, 2, 4, 6, 8]
            sage: b
            [0, 2, 4]
            sage: c           # random order
            set([word: , word: ba, word: baba, word: ab, word: bbabaa, word: abbabaab])
            sage: c == set([W(), W('ba'), W('baba'), W('ab'), W('bbabaa'), W('abbabaab')])
            True
        """
        #Initialize the results of computations
        palindromes = set()
        lengths_lps = [None] * len(self)
        lacunas = []
        
        #Initialize the first lps
        pal = self.parent()()
        palindromes.add(pal)
        
        #For all the non empty prefixes of self,
        for i in xrange(len(self)):
            
            #compute its longest $f$-palindromic suffix using the precedent lps (pal)
            pal = self[:i+1]._lps(l=len(pal),f=f)

            lengths_lps[i] = len(pal)

            if pal in palindromes: 
                lacunas.append(i)
            else :
                palindromes.add(pal)
        
        return lengths_lps, lacunas, palindromes

    def lengths_lps(self, f=None):
        r"""
        Returns the list of the length of the longest palindromic
        suffixe (lps) for each non empty prefix of self.
        
        DEFINITION:
            It corresponds to the function $G_w$ defined in [2].

        INPUT:
            f -- involution (default: None) on the alphabet of self. It must 
                 be something that WordMorphism's contructor understand 
                 (dict, str, ...).
                             
        OUTPUT:
            list -- list of the length of the longest palindromic
                    suffix (lps) for each non empty prefix of self;
                   
        REFERENCES:
            [1] Blondin Mass\'e, A., S. Brlek et S. Labb\'e, 
            Palindromic lacunas of the Thue-Morse word, Proc. GASCOM 2008 
            (June 16-20 2008, Bibbiena, Arezzo-Italia), 53--67.
            [2] Blondin Mass\'e, A., S. Brlek, A. Frosini, S. Labb\'e et S. Rinaldi,
            Reconstructing words from a fixed palindromic length sequence, 
            Proc. TCS 2008, 5th IFIP International Conference on Theoretical 
            Computer Science (September 8-10 2008, Milano, Italia), accepted.
        
        EXAMPLES:
            sage: Word().lengths_lps()             
            []
            sage: Word('a').lengths_lps()
            [1]
            sage: Word('aaa').lengths_lps()
            [1, 2, 3]
            sage: Word('abbabaabbaab').lengths_lps()         
            [1, 1, 2, 4, 3, 3, 2, 4, 2, 4, 6, 8]
            sage: Word('abbabaabbaab').lengths_lps(f='a->b,b->a')
            [0, 2, 0, 2, 2, 4, 6, 8, 4, 6, 4, 6]
        """
        return self.palindromic_lacunas_study(f=f)[0]

    def lacunas(self, f=None):
        r"""
        Returns the list of all the lacunas of self.
        
        DEFINITION:
            A lacuna is a position in a word where the longest palindromic
            suffix is not unioccurent (see [1]).

        INPUT:
            f -- involution (default: None) on the alphabet of self. It must 
                 be something that WordMorphism's contructor understand 
                 (dict, str, ...).
                             
        OUTPUT:
            list -- list of all the lacunas of self.
                   
        REFERENCES:
            [1] Blondin Mass\'e, A., S. Brlek et S. Labb\'e, 
            Palindromic lacunas of the Thue-Morse word, Proc. GASCOM 2008 
            (June 16-20 2008, Bibbiena, Arezzo-Italia), 53--67.
        
        EXAMPLES:
            sage: words.ThueMorseWord()[:100].lacunas()             
            [8, 9, 24, 25, 32, 33, 34, 35, 36, 37, 38, 39, 96, 97, 98, 99]
            sage: words.ThueMorseWord()[:100].lacunas(f={0:1,1:0}) #todo : not implemented
        """
        return self.palindromic_lacunas_study(f=f)[1]

    def lengths_unioccurrent_lps(self, f=None):
        r"""
        Returns the list of the length of the unioccurent longest palindromic
        suffixe (lps) for each non empty prefix of self. No unioccurrent lps
        are indicated by None.
        
        DEFINITION:
            It corresponds to the function $H_w$ defined in [1] and [2].

        INPUT:
            f -- involution (default: None) on the alphabet of self. It must 
                 be something that WordMorphism's contructor understand 
                 (dict, str, ...).
                             
        OUTPUT:
            list -- list of the length of the unioccurent longest palindromic
                    suffixe (lps) for each non empty prefix of self. 
                    No unioccurrent lps are indicated by None.
                   
        REFERENCES:
            [1] Blondin Mass\'e, A., S. Brlek et S. Labb\'e, 
            Palindromic lacunas of the Thue-Morse word, Proc. GASCOM 2008 
            (June 16-20 2008, Bibbiena, Arezzo-Italia), 53--67.
            [2] Blondin Mass\'e, A., S. Brlek, A. Frosini, S. Labb\'e et S. Rinaldi,
            Reconstructing words from a fixed palindromic length sequence, 
            Proc. TCS 2008, 5th IFIP International Conference on Theoretical 
            Computer Science (September 8-10 2008, Milano, Italia), accepted.
        
        EXAMPLES:
            sage: f = words.FibonacciWord()[:20]
            sage: f.lengths_unioccurrent_lps() == f.lengths_lps() 
            True
            sage: words.ThueMorseWord()[:20].lengths_unioccurrent_lps()
            [1, 1, 2, 4, 3, 3, 2, 4, None, None, 6, 8, 10, 12, 14, 16, 6, 8, 10, 12]
        """
        l = self.lengths_lps(f=f)
        for i in self.lacunas(f=f):
            l[i] = None
        return l

    def palindromes(self, f=None):
        r"""
        Returns the set of all palindrome (or $f$-palindrome) factors of self.

        INPUT:
            f -- involution (default: None) on the alphabet of self. It must 
                 be something that WordMorphism's contructor understand 
                 (dict, str, ...).
                             
        OUTPUT:
            set -- If f is None, the set of all palindrome factors of self;
                   otherwise, the set of all $f$-palindrome factors of self.
                
        EXAMPLES:
            sage: W = Words('01')
            sage: sorted(W('01101001').palindromes())
            [word: , word: 0, word: 00, word: 010, word: 0110, word: 1, word: 1001, word: 101, word: 11]
            sage: sorted(W('00000').palindromes())   
            [word: , word: 0, word: 00, word: 000, word: 0000, word: 00000]
            sage: sorted(W('0').palindromes())    
            [word: , word: 0]
            sage: sorted(W('').palindromes()) 
            [word: ]
            sage: sorted(W().palindromes())  
            [word: ]
            sage: sorted(Word('abbabaab').palindromes('a->b,b->a'))
            [word: , word: ab, word: abbabaab, word: ba, word: baba, word: bbabaa]
        """
        return self.palindromic_lacunas_study(f=f)[2]

    def defect(self, f=None):
        r"""
        Return the defect of self, i.e. $D(w)=|w|+1-|Pal(w)|$ defined in [1].

        INPUT:
            f -- involution (default: None) on the alphabet of self. It must 
                 be something that WordMorphism's contructor understand 
                 (dict, str, ...).
                             
        OUTPUT:
            integer -- If f is None, the palindrome defect of self;
                       otherwise, the $f$-palindrome defect of self.

        REFERENCES:
            [1] S. Brlek, S. Hamel, M. Nivat, C. Reutenauer, On the Palindromic Complexity
            of Infinite Words, in J. Berstel, J. Karhumaki, D. Perrin, Eds, Combinatorics
            on Words with Applications, International Journal of Foundation of Computer 
            Science, Vol. 15, No. 2 (2004) 293--306.
        
        EXAMPLES:
            sage: words.ThueMorseWord()[:100].defect()
            16
            sage: words.FibonacciWord()[:100].defect()
            0
            sage: W = Words('01')
            sage: W('000000000000').defect()
            0
            sage: W('011010011001').defect()
            2
            sage: W('0101001010001').defect()
            0
            sage: W().defect()
            0
            sage: Word('abbabaabbaababba').defect()
            2
            sage: Word('abbabaabbaababba').defect('a->b,b->a')
            4
        """
        return len(self)+1-len(self.palindromes(f=f))
    
    def is_full(self, f=None):
        r"""
        Return true if self has defect 0.
        
        DEFINITION :
            A word is full if its defect is zero (see [1]).

        INPUT:
            f -- involution (default: None) on the alphabet of self. It must 
                 be something that WordMorphism's contructor understand 
                 (dict, str, ...).
                             
        OUTPUT:
            boolean -- If f is None, whether self is full;
                       otherwise, whether self is full of $f$-palindromes.

        REFERENCES :
            [1] S. Brlek, S. Hamel, M. Nivat, C. Reutenauer, On the Palindromic Complexity
            of Infinite Words, in J. Berstel, J. Karhumaki, D. Perrin, Eds, Combinatorics
            on Words with Applications, International Journal of Foundation of Computer 
            Science, Vol. 15, No. 2 (2004) 293--306.
        
        EXAMPLES:
            sage: words.ThueMorseWord()[:100].is_full()
            False
            sage: words.FibonacciWord()[:100].is_full()
            True
            sage: Words('0')('000000000000000').is_full()
            True
            sage: Words('01')('011010011001').is_full()
            False
            sage: Words('123456789')('2194').is_full()
            True
            sage: Word().is_full()
            True
            sage: Word().is_full('a->b,b->a')
            True
            sage: w = Word('ab')
            sage: w.is_full()
            True
            sage: w.is_full('a->b,b->a')
            False
        """
        return self.defect(f=f) == 0
    
    def palindromic_closure(self, side='right', f=None):
        r"""
        Return the shortest palindrome having self as a prefix 
        (or as a suffix if side=='left').
        
        Retourne le plus petit palindrome ayant self comme prefixe
        (ou comme suffixe si side=='left').

        INPUT:
            side -- 'right' or 'left' (default: 'right') the direction of the 
                    closure
            f -- involution (default: None) on the alphabet of self. It must 
                 be something that WordMorphism's contructor understand 
                 (dict, str, ...).
                             
        OUTPUT:
            word -- If f is None, the right palindromic closure of self;
                    otherwise, the right $f$-palindromic closure of self.
                    If side is 'left', the left palindromic closure.
                    
        REFERENCES :        
            [1] de Luca, A., et A. De Luca, Pseudopalindrome closure operators 
            in free monoids, Theoret. Comput. Sci. 362 (2006) 282--300.
        
        EXAMPLES:
            sage: W = Words('1234567890')
            sage: W('1233').palindromic_closure()
            word: 123321
            sage: W('12332').palindromic_closure()
            word: 123321
            sage: W('0110343').palindromic_closure()
            word: 01103430110
            sage: W('0110343').palindromic_closure(side='left')
            word: 3430110343
            sage: W('01105678').palindromic_closure(side='left')
            word: 876501105678
            sage: w = Word('abbaba')                  
            sage: w.palindromic_closure()             
            word: abbababba
            sage: w.palindromic_closure(f='a->b,b->a')
            word: abbabaab
            sage: w.palindromic_closure(f='a->b,b->a',side='left')
            word: babaabbaba
            sage: w.palindromic_closure(f='a->b,b->b',side='left')
            Traceback (most recent call last):
            ...
            ValueError: f must be an involution
            sage: w.palindromic_closure(f='a->c,c->a',side='left')
            Traceback (most recent call last):
            ...
            ValueError: self must be in the domain of the given involution
        """
        if f is None:
            if side == 'right':
                l = len(self.lps())
                return self * self[-(l+1)::-1]
            elif side == 'left':
                l = len(self.reversal().lps())
                return self[:l-1:-1] * self
            else:
                raise ValueError, "side must be either 'left' or 'right' (not %s) " % side
        else:
            from sage.words.morphism import WordMorphism
            f = WordMorphism(f)
            
            if self not in f.domain():
                raise ValueError, "self must be in the domain of "\
                                     +"the given involution"
            
            if not f.is_involution():
                raise ValueError, "f must be an involution"
           
            if side == 'right':
                l = len(self.lps(f=f))
                return self * f(self[-(l+1)::-1])
            elif side == 'left':
                l = len(self.reversal().lps(f=f))
                return f(self[:l-1:-1]) * self
            else:
                raise ValueError, "side must be either 'left' or 'right' (not %s) " % side
    
    def iterated_palindromic_closure(self, side='right', f=None):
        r"""
        Returns the iterated ($f$-)palindromic closure of self.
                            
        INPUT:
            side -- 'right' or 'left' (default: 'right') the direction of the 
                    closure
            f -- involution (default: None) on the alphabet of self. It must 
                 be something that WordMorphism's contructor understand 
                 (dict, str, ...).
                             
        OUTPUT:
            word -- If f is None, the right iterated palindromic closure of self;
                    otherwise, the right iterated $f$-palindromic closure of self.
                    If side is 'left', the left palindromic closure.
                    
        REFERENCES :
            [1] de Luca, A., et A. De Luca, Pseudopalindrome closure operators 
            in free monoids, Theoret. Comput. Sci. 362 (2006) 282--300.        
                    
        EXAMPLES:
            sage: W = Words('123')
            sage: W('123').iterated_palindromic_closure()
            word: 1213121
            sage: W('123').iterated_palindromic_closure(side='left')
            word: 3231323
            sage: W('1').iterated_palindromic_closure()
            word: 1
            sage: W().iterated_palindromic_closure()
            word: 
            sage: W=Words('ab')                                                  
            sage: W('ab').iterated_palindromic_closure(f='a->b,b->a')            
            word: abbaab
            sage: W('ab').iterated_palindromic_closure(f='a->b,b->a',side='left')
            word: abbaab
            sage: W('aab').iterated_palindromic_closure(f='a->b,b->a')            
            word: ababbaabab
            sage: W('aab').iterated_palindromic_closure(f='a->b,b->a',side='left')
            word: abbaabbaab
            
        TESTS:
            sage: W('aab').iterated_palindromic_closure(f='a->b,b->a',side='leftt')
            Traceback (most recent call last):
            ...
            ValueError: side must be either 'left' or 'right' (not leftt) 
            sage: W('aab').iterated_palindromic_closure(f='a->b,b->b',side='left') 
            Traceback (most recent call last):
            ...
            ValueError: f must be an involution
        """
        if side == 'right':
            par = self.parent()
            return reduce(lambda r, s: (r*par([s])).palindromic_closure(f=f), 
                            self, par())
        elif side == 'left':
            if f is None:
                return self.reversal().iterated_palindromic_closure(f=f)
            else:
                from sage.words.morphism import WordMorphism
                f = WordMorphism(f)
                
                if self not in f.domain():
                    raise ValueError, "self must be in the domain of "\
                                         +"the given involution"
                
                if not f.is_involution():
                    raise ValueError, "f must be an involution"

                return f(self).reversal().iterated_palindromic_closure(f=f)

        else:
            raise ValueError, "side must be either 'left' or 'right' (not %s) " % side
    
    def is_symmetric(self, f=None):
        r"""
        Returns true if self is symmetric (or $f$-symmetric).
        
        DEFINITION :
            A word is symmetric (resp. $f$-symmetric) if it is the product 
            of two palindromes (resp. $f$-palindromes). See [1] and [2].

        INPUT:
            f -- involution (default: None) on the alphabet of self. It must 
                 be something that WordMorphism's contructor understand 
                 (dict, str, ...).
                             
        OUTPUT:
            boolean -- If f is None, whether self is symmetric;
                       otherwise, whether self is $f$-symmetric.

        REFERENCES :        
            [1] S. Brlek, S. Hamel, M. Nivat, C. Reutenauer, On the Palindromic Complexity
            of Infinite Words, in J. Berstel, J. Karhumaki, D. Perrin, Eds, Combinatorics
            on Words with Applications, International Journal of Foundation of Computer 
            Science, Vol. 15, No. 2 (2004) 293--306.
            [2] de Luca, A., et A. De Luca, Pseudopalindrome closure operators 
            in free monoids, Theoret. Comput. Sci. 362 (2006) 282--300.
        
        EXAMPLES:
            sage: W = Words('ab')
            sage: W('abbabab').is_symmetric()
            True
            sage: W('ababa').is_symmetric()
            True
            sage: W('aababaabba').is_symmetric()
            False
            sage: W('aabbbaababba').is_symmetric()
            False
            sage: W('aabbbaababba').is_symmetric('a->b,b->a')
            True
        """
        for i in range(len(self)):
            if self[:i].is_palindrome(f=f) and self[i:].is_palindrome(f=f):
                return True
        return False
            
    
    def is_square(self):
        """
        Returns true if the receiver is a square.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W('1212').is_square()
            True
            sage: W('1213').is_square()
            False
            sage: W('12123').is_square()
            False
            sage: W().is_square()
            True
        """
        if len(self) % 2 != 0:
            return False
        else:
            l = len(self) / 2
            return self[:l] == self[l:]
    
    def is_square_free(self):
        """
        Returns true if the receiver does not contain squares.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W('12312').is_square_free()
            True
            sage: W('31212').is_square_free()
            False
            sage: W().is_square_free()
            True
        """
        l = len(self)
        if l < 2:
            return True
        suff = self
        for i in xrange(0, l - 2):
            for ll in xrange(2, l-i+1, 2):
                if suff[:ll].is_square():
                    return False
            suff = suff[1:]
        return True
    
    def is_cube(self):
        """
        Returns true if the receiver is a cube.
        
        EXAMPLES:
            sage: W = Words('012')
            sage: W('012012012').is_cube()
            True
            sage: W('01010101').is_cube()
            False
            sage: W().is_cube()
            True
            sage: W('012012').is_cube()
            False
        """
        if len(self) % 3 != 0:
            return False
        l = len(self) / 3
        return self[:l] == self[l:2*l] == self[2*l:]
    
    def is_cube_free(self):
        """
        Returns true is the receiver does not contain cubes.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W('12312').is_cube_free()
            True
            sage: W('32221').is_cube_free()
            False
            sage: W().is_cube_free()
            True
        """
        l = len(self)
        if l < 3: 
            return True
        suff = self
        for i in xrange(0, l - 3):
            for ll in xrange(3, l-i+1, 3):
                if suff[:ll].is_cube():
                    return False
            suff = suff[1:]
        return True
    
        
    def is_quasiperiodic(self):
        """
        Returns true if the receiver is quasiperiodic.
        
        EXAMPLES:
            sage: W = Words('abc')
            sage: W('abaababaabaababaaba').is_quasiperiodic()
            True
            sage: W('abacaba').is_quasiperiodic()
            False
            sage: W('a').is_quasiperiodic()
            False
            sage: W().is_quasiperiodic()
            False
            sage: W('abaaba').is_quasiperiodic()
            True
        """
        l = len(self)
        
        if l <= 1:
           return False
              
        for i in range(1, l - 1):
            return_lengths = [len(x) for x in self.return_words(self[:i])]
            if return_lengths != []:
               if (max(return_lengths) <= i and self[l-i:l] == self[:i]):
                  return True
        return False    
   
        
    def quasiperiods(self):
        """
        Returns the quasiperiods of the receiver. 
        A finite or infinite word W is quasiperiodic if it can be constructed by 
        concatenations and superpositions of one of its proper factors u, 
        which is called a quasiperiod of W.     
    
        EXAMPLES:
            sage: W = Words('abc')
            sage: W('abaababaabaababaaba').quasiperiods()
            [word: aba, word: abaaba, word: abaababaaba]
            sage: W('abaaba').quasiperiods()
            [word: aba]
            sage: W('abacaba').quasiperiods()
            []
        """
        l = len(self)
        
        if l <= 1:
           return []
        
        Q = [] 
        for i in range(1, l - 1):
            return_lengths = [len(x) for x in self.return_words(self[:i])]
            if return_lengths != []:
               if (max(return_lengths) <= i and self[l-i:l] == self[:i]):
                  Q.append(self[:i])
        return Q            
    
    def commutes_with(self, other):
        """
        Returns true if the receiver commutes with other.
        
        EXAMPLES:
            sage: W = Words('12')
            sage: W('12').commutes_with(W('12'))
            True
            sage: W('12').commutes_with(W('11'))
            False
            sage: W().commutes_with(W('21'))
            True
        """
        return (self * other) == (other * self)
    
     
    def conjugate(self, pos):
        """
        Returns the conjugate at pos of the receiver.  pos can be any integer,
        the distance used is the modulo by the length of the receiver.
        
        EXAMPLES:
            sage: W = Words('12')
            sage: W('12112').conjugate(1)
            word: 21121
            sage: W().conjugate(2)
            word: 
            sage: W('12112').conjugate(8)
            word: 12121
            sage: W('12112').conjugate(-1)
            word: 21211
        """
        if self.is_empty():
            return self
        pos_mod = pos % len(self)
        return self[pos_mod:] * self[:pos_mod]
        
    def _conjugates_list(self):
        r"""
        Returns the list of conjugates of the receiver, 
        ordered from the 0-th to the (L-1)-st conjugate,
        where L is the length of the receiver.
        
        TESTS:
            sage: W = Words('abc')
            sage: W('cbbca')._conjugates_list()
            [word: cbbca, word: bbcac, word: bcacb, word: cacbb, word: acbbc]
            sage: W('abcabc')._conjugates_list()
            [word: abcabc,
             word: bcabca,
             word: cabcab,
             word: abcabc,
             word: bcabca,
             word: cabcab]
            sage: W()._conjugates_list()
            [word: ]
            sage: W('a')._conjugates_list()
            [word: a]
        """
        S = [self]
        for i in range(1,len(self)):
            S.append(self.conjugate(i))
        return S
        
    def conjugates(self):
        """
        Returns the set of conjugates of the receiver.
        
        TESTS:
            sage: W = Words('abc')
            sage: W('cbbca').conjugates() == set([W('cacbb'),W('bbcac'),W('acbbc'),W('cbbca'),W('bcacb')])
            True
            sage: W('abcabc').conjugates() == set([W('abcabc'),W('bcabca'),W('cabcab')])
            True
            sage: W().conjugates() == set([W()])
            True
            sage: W('a').conjugates() == set([W('a')])
            True
        """
        S = set([self])
        for i in range(1,self.primitive_length()):
            S.add(self.conjugate(i))
        return S
    
    def conjugate_position(self, other):
        """
        Returns the position where the reciever is conjugate with other.
        Returns None if there is no such position.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W('12113').conjugate_position(W('31211'))
            1
            sage: W('12131').conjugate_position(W('12113')) is None
            True
            sage: W().conjugate_position(W('123')) is None
            True
        """
        if len(self) != len(other):
            return None
        self, conj = self.coerce(other)
        if self == conj:
            return 0
        for l in xrange(1, len(conj) - 1):
            conj = conj.conjugate(1)
            if self == conj:
                return l
        return None
    
    def is_conjugate_with(self, other):
        """
        Returns true if the receiver is a conjugate of other.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W('11213').is_conjugate_with(W('31121'))
            True
            sage: W().is_conjugate_with(W('123'))
            False
            sage: W('112131').is_conjugate_with(W('11213'))
            False
            sage: W('12131').is_conjugate_with(W('11213'))
            True
        """
        return self.conjugate_position(other) is not None
    
    def is_cadence(self, seq):
        """
        Returns true if seq is a cadence of the receiver.
        
        A cadence is a increasing sequence of indexes that all map to the
        same symbol.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W('121132123').is_cadence([0, 2, 6])
            True
            sage: W('121132123').is_cadence([0, 1, 2])
            False
            sage: W('121132123').is_cadence([])
            True
        """
        if len(seq) == 0:
            return True
        try:
            it = iter(self)
            s = islice(it, seq[0], None).next()
            for i in xrange(1, len(seq)):
                steps = seq[i] - seq[i-1]
                for n in xrange(steps-1): it.next()
                if it.next() != s:
                    return False
        except StopIteration:
            return False
        return True
    
    def longest_common_prefix(self, other):
        """
        Return the longest common prefix of the receiver and other.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: w=W('12345')
            sage: y=W('1236777')
            sage: w.longest_common_prefix(y)
            word: 123
            sage: w.longest_common_prefix(w)
            word: 12345
            sage: y.longest_common_prefix(w)
            word: 123
            sage: y.longest_common_prefix(w)==w.longest_common_prefix(y)
            True
            sage: y.longest_common_prefix(y)==y
            True
            sage: W().longest_common_prefix(w)
            word: 
            sage: w.longest_common_prefix(W()) == w
            False
            sage: w.longest_common_prefix(W()) == W()
            True
            sage: w.longest_common_prefix(w[:3]) == w[:3]
            True
            sage: w.longest_common_prefix(w[:3]) == w
            False
            sage: Words('12')("11").longest_common_prefix(Words('1')("1"))
            word: 1
        """
        self, other = self.coerce(other)
        self_iter, other_iter = iter(self._content), iter(other._content)
        i = 0
        try:
            while True:
                if self_iter.next() != other_iter.next():
                    return self[:i]
                i += 1
        except StopIteration:  # one iterator finished
            if len(self) < len(other):
                return self
            else:
                return other
    
    def longest_common_suffix(self, other):
        """
        Return the longest common suffix of the receiver and other.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: y = W('549332345')
            sage: w = W('203945')
            sage: w.longest_common_suffix(y)
            word: 45
            sage: w.longest_common_suffix(y.reversal())
            word: 3945
            sage: w.longest_common_suffix(W())
            word: 
            sage: W().longest_common_suffix(w)
            word: 
            sage: W().longest_common_suffix(W())
            word: 
            sage: w.longest_common_suffix(w[3:]) == w[3:]
            True
            sage: w.longest_common_suffix(w[3:]) == w
            False
        """
        self, other = self.coerce(other)
        i = 0
        while(i < min(len(self), len(other)) and self._content[-(i+1)] == other._content[-(i+1)]):
            i += 1
        if i == 0:
            return self.parent()()
        return self[-i:]
    
    def prefix_function_table(self):
        """
        Returns a vector containing the length of the proper prefix-suffixes
        for all the non empty prefixes of the receiver.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('121321').prefix_function_table()
            [0, 0, 1, 0, 0, 1]
            sage: W('1241245').prefix_function_table()
            [0, 0, 0, 1, 2, 3, 0]
            sage: W().prefix_function_table()
            []
        """
        k = 0
        res = list(repeat(0, len(self)))
        for q in xrange(1, len(self)):
            while k > 0 and self._content[k] != self._content[q]:
                k = res[k-1]
            if self._content[k] == self._content[q]:
                k += 1
            res[q] = k
        return res
    
    def length_max_prefix_suffix(self):
        """
        Returns the length of the longest proper prefix-suffix of the receiver.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('121').length_max_prefix_suffix()
            1
            sage: W('1').length_max_prefix_suffix()
            0
            sage: W('1212').length_max_prefix_suffix()
            2
            sage: W('111').length_max_prefix_suffix()
            2
            sage: W().length_max_prefix_suffix() is None
            True
        """
        if len(self) == 0:
            return None
        return self.prefix_function_table()[-1]
    
    def longest_prefix_suffix(self):
        """
        Returns the longest proper prefix-suffix of the receiver
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('121212').longest_prefix_suffix()
            word: 1212
            sage: W('12321').longest_prefix_suffix()
            word: 1
            sage: W().longest_prefix_suffix() is None
            True
        """
        if len(self) == 0:
            return None
        return self[:self.length_max_prefix_suffix()]
    
    def is_overlap(self):
        """
        Returns true if the receiver is an overlap.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('12121').is_overlap()
            True
            sage: W('123').is_overlap()
            False
            sage: W('1231').is_overlap()
            False
            sage: W('123123').is_overlap()
            False
            sage: W('1231231').is_overlap()
            True
            sage: W().is_overlap()
            False
        """
        if len(self) == 0:
            return False
        return self.length_max_prefix_suffix() > len(self)/2
    
    def primitive_length(self):
        """
        Returns the length of the primitive of the word.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('1231').primitive_length()
            4
            sage: W('121212').primitive_length()
            2
        """
        l = lu = len(self)
        if l == 0:
            return 0
        p = self.prefix_function_table()
        while l > 0:
            l = p[l-1]
            if lu % (lu - l) == 0:
                return lu - l
    
    def is_primitive(self):
        """
        Returns true if the receiver is primitive.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('1231').is_primitive()
            True
            sage: W('111').is_primitive()
            False
        """
        return len(self) == self.primitive_length()
    
    def primitive(self):
        """
        Returns the primitive of the word.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('12312').primitive()
            word: 12312
            sage: W('121212').primitive()
            word: 12
        """
        return self[:self.primitive_length()]
    
    def exponent(self):
        """
        Returns the exponent of the receiver.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('1231').exponent()
            1
            sage: W('121212').exponent()
            3
            sage: W().exponent()
            0
        """
        if len(self) == 0:
            return 0
        return len(self) / self.primitive_length()
        
    def overlap_partition(self, other, delay, p=None):
        """
        Return the equivalence class of the alphabet in order that the receiver
        overlaps other with the delay given.
        
        Creation des classes d'equivalence (partition) des lettres pour que
        le chevauchement donne par le decalage ait lieu.

        EXEMPLE :        
        decalage = +3
        cheval
           abcdef

        EXAMPLES:
            sage: W = Words('chevalbdf')
            sage: cheval = W('cheval')
            sage: abcdef = W('abcdef')
            sage: cheval.overlap_partition(abcdef,3)
            {{'c', 'l'}, {'d'}, {'e'}, {'f'}, {'h'}, {'v', 'a', 'b'}}
            sage: W = Words('abcdef')
            sage: w = W('abc')
            sage: y = W('def')
            sage: w.overlap_partition(y, -3)
            {{'a'}, {'b'}, {'c'}, {'d'}, {'e'}, {'f'}}
            sage: w.overlap_partition(y, -2)
            {{'a', 'f'}, {'b'}, {'c'}, {'d'}, {'e'}}
            sage: w.overlap_partition(y, -1)
            {{'a', 'e'}, {'b', 'f'}, {'c'}, {'d'}}
            sage: w.overlap_partition(y, 0)
            {{'a', 'd'}, {'b', 'e'}, {'c', 'f'}}
            sage: w.overlap_partition(y, 1)
            {{'a'}, {'b', 'd'}, {'c', 'e'}, {'f'}}
            sage: w.overlap_partition(y, 2)
            {{'a'}, {'b'}, {'c', 'd'}, {'e'}, {'f'}}
            sage: w.overlap_partition(y, 3)
            {{'a'}, {'b'}, {'c'}, {'d'}, {'e'}, {'f'}}
            sage: w.overlap_partition(y, 4)
            {{'a'}, {'b'}, {'c'}, {'d'}, {'e'}, {'f'}}
            sage: W = Words(range(2))
            sage: w = W([0,1,0,1,0,1]); w
            word: 010101
            sage: w.overlap_partition(w, 0)
            {{0}, {1}}
            sage: w.overlap_partition(w, 1)
            {{0, 1}}
        """
        if delay < 0:
            return other.overlap_partition(self, -delay, p)
        
        self, other = self.coerce(other)
        
        #Creation of the default evolving partition
        if p == None:
            p = DisjointSet(self.alphabet(), self.parent().alphabet().to_int)
        
        #Join the classes of each pair of letters that are one above the other
        for i in range(delay, min(len(other)+delay, len(self))):
            p.join(self[i], other[i-delay])
            
        return p
        
    def relabeling(self, partition):
        """
        Return the word obtain by relabelling each letter by its
        representant in the partition. The letter is not replaced if it is
        not in the partition.
        
        Retourne le mot obtenu en remplacant chaque caractere
        de w par son representant dans la partition ou par lui-meme
        s'il n'est pas dans la partition.
        
        EXAMPLE:
        cheval
           abcdef
          lave
        
        EXAMPLES:
            sage: W = Words('chevalbdf')
            sage: cheval = W('cheval')                
            sage: abcdef = W('abcdef')
            sage: p = cheval.overlap_partition(abcdef, 3); p
            {{'c', 'l'}, {'d'}, {'e'}, {'f'}, {'h'}, {'v', 'a', 'b'}}
            sage: set(p.representants()) == set(['c', 'e', 'd', 'f', 'h', 'v'])
            True
            sage: cheval.relabeling(p)
            word: chevvc
            sage: lave = W('lave')
            sage: lave.overlap_partition(abcdef, 1, p)
            {{'c', 'e', 'l'}, {'d'}, {'f'}, {'h'}, {'v', 'a', 'b'}}
            sage: cheval.relabeling(p)
            word: chcvvc
        """
        #TODO Si une lettre du receveur n'est pas dans la partition, 
        #     prefere-t-on retourner une erreur?
        #TODO On pourrait surrement retourner un word_iterateur ou fn si
        #     self est de ce type.
        W = Words(partition.representants())
        w = []
        for c in self:
            rep_c = partition.representant_of(c)
            if rep_c is None:
                w.append(c)
            else:
                w.append(rep_c)
        return W(w)
    
    def last_position_table(self):
        """
        Returns a table (of size 256) that contains the last position of 
        each symbol in the receiver. The symbols not present in the word 
        will have a position of None
        
        EXAMPLES:
            sage: Words('01234')('1231232').last_position_table()
            [-1, 3, 6, 5, -1]
        """
        res = [-1]*len(self.alphabet())
        for (i, s) in izip(count(), self._content):
            res[s] = i
        return res
    
    def good_suffix_table(self):
        """
        Returns a table of the maximum skip you can do in order not to miss
        a possible occurrence of the receiver in a word
        
        This is a part of the boyer-moore algorithm to find factors.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('121321').good_suffix_table()
            [5, 5, 5, 5, 3, 3, 1]
            sage: W('12412').good_suffix_table()
            [3, 3, 3, 3, 3, 1]
        """
        l = len(self)
        p = self.reversal().prefix_function_table()
        res = [l - p[-1]]*(l+1)
        for i in xrange(1, l+1):
            j = l - p[i - 1]
            if res[j] > (i - p[i-1]):
                res[j] = i - p[i-1]
        return res
    
    def _pos_in(self, other, p):
        r"""
        Returns the position of the first occurrence of the receiver 
        starting at position p in other.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W('12')._pos_in(W('131231'), 2)
            2
            sage: W('12')._pos_in(W('131231'), 3) is None
            True
            sage: W('32')._pos_in(W('131231'), 0) is None
            True
        """
        lf = len(self)
        lm = len(other)
        if lf == 0 or lm == 0:
            return None
        occ = self.last_position_table()
        suff = self.good_suffix_table()
        s = p
        while s <= lm - lf:
            for j in xrange(lf-1, -1, -1):
                if self._content[j] != other._content[s+j]:
                    s += max(suff[j + 1], j - occ[other._content[s+j]])
                    break
            else:
                return s
        return None
    
    def first_pos_in(self, other):
        r"""
        Returns the position of the first occurrence of the receiver in other
        or None if the receiver is not a factor of other.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('12').first_pos_in(W('131231'))
            2
            sage: W('32').first_pos_in(W('131231')) is None
            True
        """
        self, other = self.coerce(other)
        return self._pos_in(other, 0)
        
    
    def is_factor_of(self, other):
        r"""
        Returns true if self is a factor of other.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('2113').is_factor_of(W('123121332131233121132123'))
            True
            sage: W('321').is_factor_of(W('1231241231312312312'))
            False
        """
        return self.first_pos_in(other) is not None
    
    def factor_occurrences_in(self, other):
        r"""
        Returns an iterator over all occurences (including overlapping ones)
        of this word in other in their order of appearance.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: list(W('121').factor_occurrences_in(W('121213211213')))
            [0, 2, 8]
        """
        self, other = self.coerce(other)
        if len(self) == 0:
            raise NotImplementedError, "undefined value"
        p = self._pos_in(other, 0)
        while p is not None:
            yield p
            p = self._pos_in(other, p+1)
    
    def nb_factor_occurrences_in(self, other):
        r"""
        Returns the number of times the receiver appears as a factor
        in other.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W().nb_factor_occurrences_in(W('123'))
            Traceback (most recent call last):
            ...
            NotImplementedError: undefined value
            sage: W('123').nb_factor_occurrences_in(W('112332312313112332121123'))
            4
            sage: W('321').nb_factor_occurrences_in(W('11233231231311233221123'))
            0
        """
        return len_it(self.factor_occurrences_in(other))
    
    def is_subword_of(self, other):
        """
        Returns true is the receiver is a subword of other.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W().is_subword_of(W('123'))
            True
            sage: W('123').is_subword_of(W('3211333213233321'))
            True
            sage: W('321').is_subword_of(W('11122212112122133111222332'))
            False
        """
        self, other = self.coerce(other)
        its = iter(self._content)
        try:
            s = its.next()
            for e in other._content:
                if s == e:
                    s = its.next()
            else:
                return False
        except StopIteration:
            return True
    
    def nb_subword_occurrences_in(self, other):
        r"""
        Returns the number of times the receiver appears in other as a subword.
        
        EXAMPLES:
            sage: W = Words('1234')
            sage: W().nb_subword_occurrences_in(W('123'))
            Traceback (most recent call last):
              ...
            NotImplementedError: undefined value
            sage: W('123').nb_subword_occurrences_in(W('1133432311132311112'))
            11
            sage: W('4321').nb_subword_occurrences_in(W('1132231112233212342231112'))
            0
            sage: W('3').nb_subword_occurrences_in(W('122332112321213'))
            4
        """
        self, other = self.coerce(other)
        ls = len(self)
        if ls == 0:
            raise NotImplementedError, "undefined value"
        elif ls == 1:
            return self.nb_factor_occurrences_in(other)
        elif len(other) < ls:
            return 0
        symb = self[:1]
        suffword = other
        suffsm = self[1:]
        n = 0
        cpt = 0
        i = symb.first_pos_in(suffword)
        while i is not None:
            suffword = suffword[i+1:]
            m = suffsm.nb_subword_occurrences_in(suffword)
            if m == 0: break
            n += m
            i = symb.first_pos_in(suffword)
        return n
    
    def _return_words_list(self, fact):
        r"""
        Returns the return words as a list in the order they appear in the word.
        
        TESTS:
            sage: W = Words('abc')
            sage: W('baccabccbacbca')._return_words_list(W('b'))
            [word: bacca, word: bcc, word: bac]
        """
        self, fact = self.coerce(fact)
        i = fact.first_pos_in(self)
        if i is None:
            return []
        w = self[i+1:]
        j = fact.first_pos_in(w)
        res = []
        while j is not None:
            res.append(self[i:i+j+1])
            w = w[j+1:]
            i += j+1
            j = fact.first_pos_in(w)
        return res
    
    def return_words(self, fact):
        r"""
        Returns the set of return words.  This is the set of all factors starting
        by the given factor and ending just before the next occurrence
        of this factor.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W('21331233213231').return_words(W('2')) == set([W('21331'), W('233'), W('213')])
            True
            sage: W().return_words(W('213')) == set()
            True
            sage: W('121212').return_words(W('1212')) == set([W('12')])
            True
        """
        return set(self._return_words_list(fact))
    
    def complete_return_words(self, fact):
        """
        Returns the set of return words.  This is the set of all factors starting
        by the given factor and ending just after the next occurrence
        of this factor.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W('21331233213231').complete_return_words(W('2')) == set([W('213312'), W('2332'), W('2132')])
            True
            sage: W('').complete_return_words(W('213')) == set()
            True
            sage: W('121212').complete_return_words(W('1212')) == set([W('121212')])
            True
        """
        i = fact.first_pos_in(self)
        if i is None:
            return set()
        w = self[i+1:]
        j = fact.first_pos_in(w)
        res = set()
        while j is not None:
            res.add(self[i:i+j+len(fact)+1])
            w = w[j+1:]
            i += j+1
            j = fact.first_pos_in(w)
        return res
    
    def return_words_derivate(self, fact, W=None):
        r"""
        Returns the word generated by mapping a symbol to each occurrence of 
        the return words for the given factor dropping any dangling prefix and 
        suffix.
        
        The optional set of words parameter must be over an alphabet that contains
        as much symbols as there are different return words in the receiver otherwise
        there will be some breakage in the function.  The default value for this 
        parameter always repects this property.  The symbols are attributed to the
        words in the order they are discovered.
        
        EXAMPLES:
            sage: Words('123')('12131221312313122').return_words_derivate(Words('1')('1'))
            word: 123242
        """
        self, fact = self.coerce(fact)
        idx = 0
        tab = {}
        ret = map(lambda w: tab.setdefault(w, len(tab)) + 1, self._return_words_list(fact))
        if W is None:
            W = Words(xrange(1, len(tab)+1)) 
        return W(ret)
    
    def delta(self):
        """
        Returns the delta equivalent of the receiver. This is the word 
        composed of the length of consecutive runs of the same symbol.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('22112122').delta()
            word: 22112
            sage: W('555008').delta()
            word: 321
            sage: W().delta()
            word: 
        """
        if len(self) == 0:
            return Words([])()
        ss = self[0]
        c = 0
        v = list()
        max_c = 0
        for s in self:
            if s == ss:
                c += 1
                if c > max_c:
                    max_c = c
            else:
                v.append(c)
                ss = s
                c = 1
        v.append(c)
        return Words(xrange(1, max_c+1))(v)
    
    def delta_inv(self, W=Words([1, 2]), s=None):
        """
        Returns the inverse of the delta operator applied to the receiver.
        
        The symbols in the returned word will start at the specified symbol
        or the first one if None is specified (the default). The default
        alphabet is \{1, 2\}
        
        EXAMPLES:
            sage: W = Words([1, 2])
            sage: W([2, 2, 1, 1]).delta_inv()
            word: 112212
            sage: W([1, 1, 1, 1]).delta_inv(Words('123'))
            word: 1231
            sage: W([2, 2, 1, 1, 2]).delta_inv(s=2)
            word: 22112122
        """
        if not all(imap(isint, self.alphabet())):
            raise ValueError, "delta_inv() can only be applied to word composed of integer symbols"
        if len(self) == 0:
            return W()
        if not isinstance(W, Words):
            raise TypeError, "W must be an instance of Words"
        if s is None:
            s = W.alphabet().to_sym(0)
        if s not in W.alphabet():
            raise ValueError, "starting symbol not in alphabet"
        v = []
        
        p = W.alphabet().to_int(s)
        al = cycle(imap(W.alphabet().to_sym, chain(xrange(p, len(W.alphabet())), xrange(p))))
        al.next()
        for e in self:
            v += ([s] * e)
            s = al.next()
        return W(v)
    
    def delta_derivate(self, W=None):
        """
        Returns the derivative under delta for the reciver.
        
        EXAMPLES:
            sage: W = Words('12')
            sage: W('12211').delta_derivate()
            word: 22
            sage: W('1').delta_derivate(Words([1]))
            word: 1
            sage: W('2112').delta_derivate()
            word: 2
            sage: W('2211').delta_derivate()
            word: 22
            sage: W('112').delta_derivate()
            word: 2
            sage: W('11222').delta_derivate(Words([1, 2, 3]))
            word: 3
        """
        d = self.delta()
        if len(d) == 0:
            return d
        if W is None:
            W = d.parent()
        if d[0] != W.alphabet().max_sym():
            d = d[1:]
        if d[-1] != W.alphabet().max_sym():
            d = d[:-1]
        return d
    
    def delta_derivate_left(self, W=None):
        """
        Returns the derivative under delta for the reciver.
        
        EXAMPLES:
            sage: W = Words('12')
            sage: W('12211').delta_derivate_left()
            word: 22
            sage: W('1').delta_derivate_left(Words([1]))
            word: 1
            sage: W('2112').delta_derivate_left()
            word: 21
            sage: W('2211').delta_derivate_left()
            word: 22
            sage: W('112').delta_derivate_left()
            word: 21
            sage: W('11222').delta_derivate_left(Words([1, 2, 3]))
            word: 3
        """
        d = self.delta()
        if len(d) == 0:
            return d
        if W is None:
            W = d.parent()
        if d[0] != W.alphabet().max_sym():
            d = d[1:]
        return d
    
    def delta_derivate_right(self, W=None):
        """
        Returns the right derivative under delta for the reciver.
        
        EXAMPLES:
            sage: W = Words('12')
            sage: W('12211').delta_derivate_right()
            word: 122
            sage: W('1').delta_derivate_right(Words([1]))
            word: 1
            sage: W('2112').delta_derivate_right()
            word: 12
            sage: W('2211').delta_derivate_right()
            word: 22
            sage: W('112').delta_derivate_right()
            word: 2
            sage: W('11222').delta_derivate_right(Words([1, 2, 3]))
            word: 23
        """
        d = self.delta()
        if len(d) == 0:
            return d
        if W is None:
            W = d.parent()
        if d[-1] != W.alphabet().max_sym():
            d = d[:-1]
        return d
    
    def phi(self):
        r"""
        Applies the phi function to the receiver and returns the result.
        
        INPUT:
            self -- must be a word over integers
                    
        OUTPUT:
            word -- the result of the phi function
            
        EXAMPLES:
            sage: W = Words([1, 2])
            sage: W([2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2]).phi()
            word: 222222
            sage: W().phi()
            word: 
            sage: W([2, 1, 2, 2, 1, 2, 2, 1, 2, 1]).phi()
            word: 212113
        """
        if self.is_empty():
            return self
        m = self
        v = []
        s_max = 0
        while len(m) > 1:
            v.append(m[0])
            if m[0] > s_max:
                s_max = m[0]
            m = m.delta()
        v.append(m[0])
        if m[0] > s_max:
            s_max = m[0]
        return Words(xrange(1, s_max+1))(v)
        
    def phi_inv(self, W=None):
        r"""
        Applied the inverse of the phi function and returns the result.
        
        INPUT:
            self -- must be a word over the integers
            W -- the set of words of the result. must also be over the integers
        
        OUTPUT:
            word -- the inverse of the phi function
        
        EXAMPLES:
            sage: W = Words([1, 2])
            sage: W([2, 2, 2, 2, 1, 2]).phi_inv()
            word: 22112122
            sage: W([2, 2, 2]).phi_inv(Words([2, 3]))
            word: 2233
        """
        if W is None:
            W = self.parent()
        if self.is_empty():
            return W()
        v = self.parent()((self[-1],))
        for i in xrange(len(self) - 2, -1, -1):
            v = v.delta_inv(W, self[i])
        return v
    
    def _phi_inv_tab(self, tab):
        r"""
        Specialized version of phi_inv() for long or incremental words.
        
        TESTS:
            sage: Words([1, 2])([1, 1, 2, 2])._phi_inv_tab([2])
            word: 12211
        """
        res = self.delta_inv(s=tab[0])
        res = res[1:]
        for i in xrange(1, len(tab)):
            res = res.delta_inv(s=tab[i])
        return res
    
    def is_smooth_prefix(self):
        r"""
        Returns whether the receiver is the prefix of a smooth word of not.
        
        INPUT:
            self -- must be a word over the integer to get somthing else than False
            
        OUTPUT:
            boolean -- whether the receiver is a smooth prefix or not
        
        EXAMPLES:
            sage: W = Words([1, 2])
            sage: W([1, 1, 2, 2, 1, 2, 1, 1]).is_smooth_prefix()
            True
            sage: W([1, 2, 1, 2, 1, 2]).is_smooth_prefix()
            False
        """
        m = self
        while len(m) > 1:
            m = m.delta_derivate_right()
            if m not in self.parent():
                return False
        return True
    
    def is_lyndon(self):
        """
        Returns true if the reciever is a lyndon word.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('123132133').is_lyndon()
            True
            sage: W().is_lyndon()
            True
            sage: W('122112').is_lyndon()
            False
        """
        if len(self) == 0:
            return True
        s = self._content[0]
        for (e, i) in izip(self[1:]._content, count(1)):
            if s < e:
                continue
            if not self < self[i:]:
                return False
        return True
        
    def BWT(self):
        """
        Returns the Burrows-Wheeler Transform (BWT) of the receiver,
        which is obtained by first listing the conjugates of the
        receiver in lexicographic order and then concatenating the
        final letters of the conjugates in this order.
        
        REFERENCES:
        M. Burrows, D.J. Wheeler, "A block-sorting lossless data
        compression algorithm", HP Lab Technical Report, 1994, available
        at http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.html
        
        EXAMPLES:
            sage: W = Words('abc')
            sage: W('abaccaaba').BWT()
            word: cbaabaaca
            sage: W('abaab').BWT()
            word: bbaaa
            sage: W('bbabbaca').BWT()
            word: cbbbbaaa
            sage: W('aabaab').BWT()
            word: bbaaaa
            sage: Word().BWT()
            word: 
            sage: W('a').BWT()
            word: a
        """
        if self.is_empty():
           return self
        conjugates = self._conjugates_list()
        conjugates.sort()
        return self.parent()([x[len(x)-1] for x in conjugates])
    
    def _Duval_algorithm(self):
        """
        TESTS:
            sage: Words('01')('010010010001000')._Duval_algorithm()
            (01.001.001.0001)
            sage: Words('123')('122113112212')._Duval_algorithm()
            (122.113.112212)
        """
        t = Factorization()
        cm = self
        c = iter(cm)
        cc = iter(cm)
        cc.next()
        i = 0
        d = 1
        j = k = 1
        l = len(cm)
        
        while k < l:
            c, c_s = peek_it(c)
            cc, cc_s = peek_it(cc)
            if c_s < cc_s:
                cc.next()
                k += 1
                j = k
                d = k - i
                c = iter(cm)
            elif c_s == cc_s:
                cc.next()
                k += 1
                if (k - j) == d:
                    j = k
                    c = iter(cm)
                else:
                    c.next()
            else:
                i += d
                while i <= j:
                    i += d
                    t.append(cm[:d])
                    cm = cm[d:]
                c = iter(cm)
                cc = iter(cm)
                cc.next()
                i = j
                j += 1
                k = j
                d = 1
        i += d
        while i <= j:
            i += d
            t.append(cm[:d])
            cm = cm[d:]
        return t
    
    def Duval_factorization(self):
        r"""
        Returns the Duval factorization of the word.
        
        FIXME: apparently this means nothing.  And this does not
               even return a proper factorization.  So maybe it
               should go.
        
        OUTPUT:
            list -- the list of factors obtained
            
        EXAMPLES:
            sage: Words('01')('010010010001000').Duval_factorization()
            (01.001.001.0001)
        """
        return self._Duval_algorithm()
    
    def Lyndon_factorization(self):
        r"""
        Returns the Lyndon factorization of the word.
        
        OUTPUT:
            list -- the list of factors obtained
        
        EXAMPLES:
            sage: Words('01')('010010010001000').Lyndon_factorization()
            (01.001.001.0001.0.0.0)
            sage: Words('ab')('abbababbaababba').Lyndon_factorization()
            (abb.ababb.aababb.a)
        """
        tab = self._Duval_algorithm()
        l = sum(imap(len, tab))
        if l < len(self):
            tab += self[l:]._Duval_algorithm()
        return tab
    
    def standard_factorization(self):
        r"""
        Returns the standard factorization of word.
        
        OUTPUT:
            list -- the list of factors
        
        EXAMPLES:
            sage: Words('01')('0010110011').standard_factorization()
            (001011.0011)
            sage: Words('123')('1223312').standard_factorization()
            (12233.12)
        """
        suff = self[1:]
        for l in xrange(1, len(self)):
            pref = self[:l]
            if pref.is_lyndon() and suff.is_lyndon():
                return Factorization([pref, suff])
            suff = suff[1:]
        return Factorization(self, self.parent()())
    
    def standard_factorization_of_Lyndon_factorization(self):
        r"""
        Returns the standard factorization of the Lyndon factorization of the word.
        
        OUTPUT:
            list of lists -- the factorization
        
        EXAMPLES:
            sage: Words('123')('1221131122').standard_factorization_of_Lyndon_factorization()
            [(12.2), (1.13), (1.122)]
        """
        return map(FiniteWord.standard_factorization, self.Lyndon_factorization())
    
    def crochemore_factorization(self):
        r"""
        Returns the Crochemore factorization of the word as an ordered list of
        factors.
        
        The Crochemore factorization of a word w is the unique factorization
        (x_1, x_2, ..., x_n) of w with each xi satisfying either:
        
        C1. x_i is a letter that does not appear in u = x_1...x_{i-1};
        C2. x_i is the longest prefix of v = x_i...x_n that also has an 
        occurrence beginning within u = x_1...x_{i-1}.
        
        This is not a very good implementation, and should be improved.
        
        EXAMPLES:
            sage: x = Words('ab')('abababb')
            sage: x.crochemore_factorization()
            (a.b.abab.b)
            sage: mul(x.crochemore_factorization()) == x
            True
            sage: y = Words('abc')('abaababacabba')
            sage: y.crochemore_factorization()
            (a.b.a.aba.ba.c.ab.ba)
            sage: mul(y.crochemore_factorization()) == y
            True
            sage: x = Words([0, 1])([0,1,0,1,0,1,1])
            sage: x.crochemore_factorization()
            (0.1.0101.1)
            sage: mul(x.crochemore_factorization()) == x
            True
        """
        c = Factorization([self[:1]])
        u = self[:sum(map(len,c))] # = x_1 ... x_{i-1}
        v = self[sum(map(len,c)):] # = x_i ... x_n
        while v:
            # C1. x_i is a letter that does not appear in u = x_1...x_{i-1}
            if v[0] not in u:
                c.append(v[:1])
            else:
            # C2. x_i is the longest prefix of v = x_i...x_n that also has an
            #     occurrence beginning within u = x_1...x_{i-1}.
                xi = v
                while True:
                    if xi.first_pos_in(self) < len(u):
                        c.append(xi)
                        break
                    else:
                        xi = xi[:-1]
            u = self[:sum(map(len,c))] # = x_1 ... x_{i-1}
            v = self[sum(map(len,c)):] # = x_i ... x_n
        return c
            
    def is_balanced(self, q=1):
        r"""
        Returns whether or not the receiver is q-balanced.
        
        INPUT:
            q -- integer (default 1), the balance level
        
        OUTPUT:
            boolean -- the result
            
        EXAMPLES:
            sage: Words('123')('1213121').is_balanced()
            True
            sage: Words('12')('1122').is_balanced()
            False
            sage: Words('123')('121333121').is_balanced()
            False
            sage: Words('123')('121333121').is_balanced(2)
            False
            sage: Words('123')('121333121').is_balanced(3)
            True
            sage: Words('12')('121122121').is_balanced()
            False
            sage: Words('12')('121122121').is_balanced(2)
            True
            sage: Words('12')('121122121').is_balanced(-1)
            Traceback (most recent call last):
            ...
            TypeError: the balance level must be a positive integer
            sage: Words('12')('121122121').is_balanced(0)
            Traceback (most recent call last):
            ...
            TypeError: the balance level must be a positive integer
            sage: Words('12')('121122121').is_balanced('a')
            Traceback (most recent call last):
            ...
            TypeError: the balance level must be a positive integer
        """
        if not isint(q) or q <= 0:
           raise TypeError, "the balance level must be a positive integer"
        for i in xrange(2, len(self)):
            tab = [None] * len(self.alphabet())
            for j in xrange(len(tab)):
                tab[j] = set()
            for fact in self.factor_iterator(i):
                for (n, sym) in izip(count(), self.alphabet()):
                    tab[n].add(self.parent()(sym).nb_factor_occurrences_in(fact))
            for t in tab:
                if len(t) > q+1:
                    return False
        return True
    
    def freq(self):
        r"""
        Returns a table of the frequencies of the symbols
        
        OUTPUT:
            dict -- symbols associated to their frequency
            
        EXAMPLES:
            sage: Words('123')('1213121').freq()    # keys appear in random order
            {'1': 4, '2': 2, '3': 1}
            
        TESTS:
            sage: f = Words('123')('1213121').freq()
            sage: f['1'] == 4
            True
            sage: f['2'] == 2
            True
            sage: f['3'] == 1
            True
        """
        res = dict()
        for sym in self.alphabet():
            res[sym] = 0
        for s in self:
            res[s] += 1
        return res
        
    def parikh_vector(self):
        """
        Returns the Parikh vector of the receiver,
        i.e., the vector containing the number of occurrences 
        of each letter, given in the order of the alphabet.
        
        EXAMPLES:
            sage: Word('aabaa').parikh_vector()
            [4, 1]
            sage: Word('aabaacaccab').parikh_vector()
            [6, 2, 3]
            sage: Words('abc')('aabaa').parikh_vector()
            [4, 1, 0]
            sage: Word().parikh_vector()
            []
            sage: Word('a').parikh_vector()
            [1]
            sage: Words('abc')('a').parikh_vector()
            [1, 0, 0]
            sage: Words('ab')().parikh_vector()
            [0, 0]
            sage: Words('abc')().parikh_vector()
            [0, 0, 0]
            sage: Words('abcd')().parikh_vector()
            [0, 0, 0, 0]
        """
        v = [0] * self.parent().dimension()
        for c in self._content :
            v[c] += 1
        return v            
    
    def apply_morphism(self,morphism,operation='*'):
        """
        Returns the word obtained by applying the morphism to self.
        
        INPUT:
            morphism -- Can be one of the following:
                1. a dictionary with the letters of self as keys.
                2. an instance of the morphism class.
        
        EXAMPLES:
            sage: n0, n1 = matrix(2,[1,1,1,0])**2, matrix(2,[2,1,1,0])**2
            sage: n = {0:n0, 1:n1}
            sage: w = words.ChristoffelWord(3,5)
            sage: w.apply_morphism(n)
            [18045  7561]
            [11069  4638]
        """
        lettre = self[0]
        if not morphism.has_key(lettre):
            raise TypeError, "The morphism is not defined on %s" % lettre
        result = morphism[lettre]
        for lettre in self[1:]:
            if not morphism.has_key(lettre):
                raise TypeError, "The morphism is not defined on %s" % lettre
            if operation == '*':
                result *= morphism[lettre]
            elif operation == '+':
                result += morphism[lettre]
            else:
                raise NotImplementedError
        return result
    
    def count(self, letter):
        """
        Count the number of occurrences of letter in self.
        
        EXAMPLES:
            sage: Words('ab')('abbabaab').count('a')
            4
        """
        return self.parent()([letter]).nb_factor_occurrences_in(self)

    def suffix_trie(self):
        r"""
        Returns the suffix trie of self.

        The suffix trie of a finite word w is a data structure representing
        the factors of w. It is a tree whose edges are labelled with
        letters of w, and whose leafs correspond to suffixes of w.

        See sage.words.suffix_trees.SuffixTrie? for more information.

        EXAMPLES:
            sage: w = Words("cao")("cacao")
            sage: w.suffix_trie()
            Suffix Trie of the word: cacao

            sage: w = Words([0,1])([0,1,0,1,1])
            sage: w.suffix_trie()
            Suffix Trie of the word: 01011
        """
        from sage.words.suffix_trees import SuffixTrie
        return SuffixTrie(self)

    def implicit_suffix_tree(self):
        r"""
        Returns the implicit suffix tree of self.

        The suffix tree of a word w is a compactification of the suffix
        trie for w. The compactification removes all nodes that have
        exactly one incoming edge and exactly one outgoing edge. It
        consists of two components: a tree and a word. Thus, instead of
        labelling the edges by factors of w, we can labelled them by
        indices of the occurrence of the factors in w. 

        See sage.words.suffix_trees.ImplicitSuffixTree? for more information.

        EXAMPLES:
            sage: w = Words("cao")("cacao")
            sage: w.implicit_suffix_tree()
            Implicit Suffix Tree of the word: cacao
            
            sage: w = Words([0,1])([0,1,0,1,1])
            sage: w.implicit_suffix_tree()
            Implicit Suffix Tree of the word: 01011
        """
        from sage.words.suffix_trees import ImplicitSuffixTree
        return ImplicitSuffixTree(self)

    def suffix_tree(self):
        r"""
        Alias for implicit_suffix_tree().
        
        EXAMPLES:
            sage: Words('ab')('abbabaab').suffix_tree()
            Implicit Suffix Tree of the word: abbabaab
        """
        return self.implicit_suffix_tree()

    def number_of_factors(self,n=None):
        r"""
        Count the number of distinct factors of self.

        INPUT:
            n -- an integer, or None.

        OUTPUT:
            If n is an integer, returns the number of distinct factors
            of length n. If n is None, returns the total number of
            distinct factors.

        EXAMPLES:
            sage: w = Words([1,2,3])([1,2,1,2,3])
            sage: w.number_of_factors()
            13
            sage: map(w.number_of_factors, range(6))
            [1, 3, 3, 3, 2, 1]

            sage: Words('123')('1213121').number_of_factors()
            22
            sage: Words('123')('1213121').number_of_factors(1)
            3

            sage: Words('a')('a'*100).number_of_factors()
            101
            sage: Words('a')('a'*100).number_of_factors(77)
            1

            sage: Words([])().number_of_factors()
            1
            sage: Words([])().number_of_factors(17)
            0

            sage: blueberry = Word("blueberry")
            sage: blueberry.number_of_factors()
            43
            sage: map(blueberry.number_of_factors, range(10))
            [1, 6, 8, 7, 6, 5, 4, 3, 2, 1]
        """
        return self.suffix_tree().number_of_factors(n)

    def factor_iterator(self,n=None):
        r"""
        Generate distinct factors of self.

        INPUT:
            n -- an integer, or None.

        OUTPUT:
            If n is an integer, returns an iterator over all distinct
            factors of length n. If n is None, returns an iterator
            generating all distinct factors.

        EXAMPLES:
            sage: w = Words('123')('1213121')
            sage: sorted( w.factor_iterator(0) )
            [word: ]
            sage: sorted( w.factor_iterator(10) )
            []
            sage: sorted( w.factor_iterator(1) )
            [word: 1, word: 2, word: 3]
            sage: sorted( w.factor_iterator(4) )
            [word: 1213, word: 1312, word: 2131, word: 3121]
            sage: sorted( w.factor_iterator() )
            [word: , word: 1, word: 12, word: 121, word: 1213, word: 12131, word: 121312, word: 1213121, word: 13, word: 131, word: 1312, word: 13121, word: 2, word: 21, word: 213, word: 2131, word: 21312, word: 213121, word: 3, word: 31, word: 312, word: 3121]

            sage: u = Words([1,2,3])([1,2,1,2,3])
            sage: sorted( u.factor_iterator(0) )
            [word: ]
            sage: sorted( u.factor_iterator(10) )
            []
            sage: sorted( u.factor_iterator(1) )
            [word: 1, word: 2, word: 3]
            sage: sorted( u.factor_iterator(5) )
            [word: 12123]
            sage: sorted( u.factor_iterator() )
            [word: , word: 1, word: 12, word: 121, word: 1212, word: 12123, word: 123, word: 2, word: 21, word: 212, word: 2123, word: 23, word: 3]

            sage: xxx = Word("xxx")
            sage: sorted( xxx.factor_iterator(0) )
            [word: ]
            sage: sorted( xxx.factor_iterator(4) )
            []
            sage: sorted( xxx.factor_iterator(2) )
            [word: xx]
            sage: sorted( xxx.factor_iterator() )
            [word: , word: x, word: xx, word: xxx]

            sage: e = Word()
            sage: sorted( e.factor_iterator(0) )
            [word: ]
            sage: sorted( e.factor_iterator(17) )
            []
            sage: sorted( e.factor_iterator() )
            [word: ]

        TESTS:
            sage: type( Words('cao')('cacao').factor_iterator() )
            <type 'generator'>
        """
        return self.suffix_tree().factor_iterator(n)

    def factor_set(self):
        r"""
        Returns the set of factors of self.

        EXAMPLES:
            sage: Words('123')('1213121').factor_set()   # random
            Set of elements of <generator object at 0xa8fde6c>
            sage: sorted(  Words([1,2,3])([1,2,1,2,3]).factor_set()  )
            [word: , word: 1, word: 12, word: 121, word: 1212, word: 12123, word: 123, word: 2, word: 21, word: 212, word: 2123, word: 23, word: 3]
            sage: sorted(  Words("x")("xx").factor_set()  )
            [word: , word: x, word: xx]
            sage: set( Words([])().factor_set() )
            set([word: ])
        """
        return Set(self.factor_iterator())

#######################################################################
#                                                                     #
#                          Infinite words                             #
#                                                                     #
#######################################################################

class InfiniteWord(GenericWord):
    def __init__(self, content, parent):
        r"""
        TESTS:
            sage: sage.words.word.InfiniteWord(sage.words.word_content.MakeContent(lambda x: x%2), Words(range(2)))
            Infinite word over [0, 1]
        """
        super(InfiniteWord, self).__init__(content, parent)
        
    def _repr_(self):
        r"""
        Returns a string representation of the object
        
        TESTS:
            sage: Words([0, 1])(lambda n: n%2)._repr_()
            'Infinite word over [0, 1]'
        """
        return "Infinite word over %s" % self.alphabet().string_rep()
